#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    using LL = long long;
    static const LL MOD = 1e9 + 7;
    LL dfs(LL n)
    {
        if (n == 0)
            return 1;
        if (n == 2)
            return 20;
        LL half = n / 2;
        LL res;
        if (half % 2 == 0)
        {
            LL tmp = dfs(half);
            res = tmp * tmp;
        }
        else
        {
            LL tmp = dfs(half - 1);
            res = tmp * tmp;
            res = ((res % MOD) * 20) % MOD;
        }
        res %= MOD;
        return res;
    }
    int countGoodNumbers(long long n) {
        LL res = n % 2 == 0 ? 1 : 5;
        n = n / 2 * 2;
        return (res * dfs(n)) % MOD;
    }
};